package com.zhn;
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      public void add(int newval) {
          ListNode newNode = new ListNode(newval);
          if(this.next == null)
              this.next = newNode;
          else
              this.next.add(newval);
      }
      // 打印链表
      public void print() {
          System.out.print(this.val);
          if(this.next != null)
          {
              System.out.print("-->");
              this.next.print();
          }
      }
  }
public class ReverseList {
    public static void main(String[] args) {
        ListNode node = new ListNode();
        for(int i = 1; i < 10;i++){
            node.add(i);
        }
        System.out.println("链表数据");
        node.print();
        System.out.println("执行反转");
        ListNode listNode = reverseList(node);
        listNode.print();
    }
 //递归解法
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
    //双指针解法:
//    public ListNode reverseList(ListNode head) {
//        ListNode pre = null;
//        ListNode cur = head;
//        while(cur != null ){
//            ListNode temp = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = temp;
//        }
//        return pre;
//    }

}
